The present invention relates to binary adder circuits and techniques, and more specifically to a binary look-ahead adder employing a carry generation tree.
A carry look-ahead adder can be contrasted with a simpler, but usually slower, ripple carry adder. In a ripple carry adder, each bit of the adder must wait for the carry output from less significant bits. With reference to FIG. 1, however, a carry look-ahead adder 10 includes a GP conversion circuit 12, including a plurality of GP generators, adders and a carry generation tree 14. The carry generation tree 14 operates to calculate all the carry outputs at once. Thus, instead of having to wait for the output to “ripple” up to the most significant bit, the entire result can be computed, in theory, with significantly less delay.
The conventional carry generation tree 14 is implemented using operators, reducers, and repeaters. The carry look-ahead adder 10 of FIG. 1 is a 4-bit adder, and thus the carry generation tree 14 is relatively simple: it contains an operator 16 and two reducers 18 that receive the outputs of the individual adders from the GP conversion circuit 12 and produce the carry out signal. A carry generation tree 24 for a more complex, 8-bit adder is illustrated in FIG. 2. With outputs from eight adders being received into the carry generation tree 24, there are more operators 16 employed in the circuit to produce the carry out signal.
While carry look-ahead adders are theoretically faster than ripple carry adders, they have some problems: the conventional technique for using the operators, reducers, and repeaters permits so-called “tri-connected” operators 26, in which the outputs from two operators 16 in a previous stage are input into an operator 16b at a next stage in the tree. This structure significantly reduces the speed of the tree, at least in part because of an attendant increase in the number of transistors found in critical paths through tri-connected operators and increases capacitive loads. This problem is exacerbated when the carry generation tree is designed for a non-2^n bit adder.
Accordingly, there is a need in the art for new methods and apparatus for implementing the carry generation tree, specifically to improve the speed therethrough.